/*
 * 求子数组的最大和（数组）
 * 方法：
 *     1.暴力法；
 *     2.动态规划（编程之美，P186）；
 *
 */

#include <stdio.h>
#include <stdlib.h>

//force
int find_subarray_force(char * array, int number)
{
    int first_element = 0;
    int end_element = 0;
    int max_sum = array[first_element];
    while (first_element < number) {
        int sum = array[first_element];
        for (int i = first_element+1; i < number; ++i) {
            sum += array[i];
            if (sum > max_sum) {
                max_sum = sum;
                end_element = i;
            }
        }
        first_element++;
    }
    return max_sum;
}

//dp
int find_subarray_dp(char * array, int number)
{
    int max_sum = array[0];
    int sum = array[0];
    for (int i = 1; i < number; ++i) {
        sum += array[i];
        if (sum < array[i]) {
            sum = array[i];
        }
        if (max_sum < sum) {
            max_sum = sum;
        }
    }
    return max_sum;
}

//half solve

int main()
{
    char array[] = {1, -2, 3, 10, -4, 7, 2, -5};
    printf("%d\n", find_subarray_force(array, 8));
    printf("%d\n", find_subarray_dp(array, 8));
    return 0;
}

